package dp_algorithm.nowcoder.easy;

import java.util.Scanner;

/**
 * @author Stark
 * @description 连续最大和
 * https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?
 * tpId=85&&tqId=29858&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
 * @date 2022/4/23 11:26
 **/
public class ContinueMaxSum {
    static int choice = 2;
    public static void main(String[] args) {
        //八嘎方法
        if(choice == 1) {
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) {
                int n = in.nextInt();
                int[] arr = new int[n];
                //标志位,用于判断输入数据中是否全为负数
                int flag = 0;
                int max = Integer.MIN_VALUE;
                for (int i = 0; i < n; i++) {
                    arr[i] = in.nextInt();
                    if (arr[i] > max)
                        max = arr[i];
                    if (arr[i] >= 0)
                        flag = 1;
                }
                if (flag == 0)
                    //输入全为负数,直接输出最大的负数即可
                    System.out.println(max);
                else {
                    int i = 0;
                    while (i < n && arr[i] < 0)
                        i++;
                    long retSum = arr[i], curSum = arr[i];
                    i++;
                    for (; i < n; i++) {
                        if (arr[i] + curSum < 0) {
                            curSum = 0;
                        } else {
                            curSum += arr[i];
                            if (curSum > retSum) {
                                retSum = curSum;
                            }
                        }
                    }
                    System.out.println(retSum);
                }
            }
        }

        //使用动态规划,状态方程
        if(choice == 2){
            Scanner in = new Scanner(System.in);
            while (in.hasNextInt()) {
                int n = in.nextInt();
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = in.nextInt();
                }
                int maxSum = arr[0];
                int curSum = arr[0];
                for (int i = 1; i < arr.length; i++) {
                    //选出之前的子序列加上arr[i]之后和arr[i]哪个大
                    curSum = Math.max(curSum + arr[i],arr[i]);
                    if(curSum > maxSum)
                        maxSum = curSum;
                }
                System.out.println(maxSum);
            }
        }
    }
}
